Find the difference between strings

Time: O(N); Space: O(N); easy

Given two strings S and T which consist of only lowercase letters. String T is generated by random shuffling string S and then add one more letter at a random position. Find the letter that was added in T.

Example:

Input: s = “abcd”; t = “abcde”

Output: ‘e’

Explanation:

• ‘e’ is the letter that was added

import operator

from functools import reduce

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def findTheDifference(self, s, t) -> str:
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        return chr(reduce(operator.xor, map(ord, s), 0) ^ reduce(operator.xor, map(ord, t), 0))

import random
import string   # string.ascii_lowercase => 'abcdefghijklmnopqrstuvwxyz'

if __name__ == '__main__':
    s = "abcd"
    ltr = random.choice(string.ascii_lowercase)
    tmp = list(s)
    random.shuffle(tmp)
    tmp.append(ltr)
    t = ''.join(tmp)
    # print(ltr, ': ', t)
    a = Solution1()
    assert a.findTheDifference(s, t) == ltr

class Solution2(object):
    def findTheDifference(self, s, t) -> str:
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        t = list(t)
        s = list(s)
        for ltr in s:
            t.remove(ltr)
        return t[0]

s = "abcd"
t = 'adcbk'
a = Solution2()
assert a.findTheDifference(s, t) == 'k'

import operator
from functools import reduce

class Solution3(object):
    def findTheDifference(self, s, t) -> str:
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        # print(list(map(ord, s + t)))    # [97, 98, 99, 100, 97, 100, 99, 98, 107]
        return chr(reduce(operator.xor, map(ord, s + t)))

s = "abcd"
t = 'adcbk'
a = Solution3()
assert a.findTheDifference(s, t) == 'k'

import collections

class Solution4(object):
    def findTheDifference(self, s, t) -> str:
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        # print(collections.Counter(t))   # Counter({'a': 1, 'd': 1, 'c': 1, 'b': 1, 'k': 1})
        return list((collections.Counter(t) - collections.Counter(s)))[0]

s = "abcd"
t = 'adcbk'
a = Solution4()
assert a.findTheDifference(s, t) == 'k'

class Solution5(object):
    def findTheDifference(self, s, t) -> str:
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        s, t = sorted(s), sorted(t)
        # print(list(zip(s,t)))        # [('a', 'a'), ('b', 'b'), ('c', 'c'), ('d', 'd')]
        return t[-1] if s == t[:-1] else [x[1] for x in zip(s, t) if x[0] != x[1]][0]

sol = Solution1()
s = "abcd"
t = 'adcbk'
assert sol.findTheDifference(s, t) == 'k'

See also:

https://leetcode.com/problems/find-the-difference

https://www.lintcode.com/problem/find-the-difference